今天來看看 QSVT 的基本框架實作,我們使用的是 Qiskit;完整的程式碼在這裡!
首先,我們定義函式 QSVT(...)
,其接受的參數有:
A
:QSVT 的目標矩陣
phi_seq
:角度序列;我們預設角度慣例 (convention) 是 R
,以符合 QSVT 文獻。如果輸入慣例是 Wx
或 Wz
,我們需要先轉換慣例。
convention = R
:指定慣例 (預設是 R
)real_only = True
:當我們以多項式 逼近任意實函數 時,為了有效率地計算出 同時又滿足定理需求 (關於多項式的限制,我們在幾天前的定理沒有談到),經常 的實部可以確實逼近 ,但 的虛部卻是雜亂的。因此我們希望「只取」 的實部,並設法將 的虛部抵銷。換句話說我們需要:
其中 是 的實部且 是 的複共軛。將 real_only
設為 True
代表我們希望擺脫 phi_seq
所對應的多項式虛部。
在 QSVT 中,我們的操作對象是 A
的 block-encoding U
。一個具體的 block-encoding 策略是:
其直截了當的實作方法是:
def block_encode(A: np.ndarray) -> np.ndarray:
n = A.shape[0]
A_dag = np.conjugate(np.transpose(A))
I_AAd = np.identity(n) - A @ A_dag
eigval, eigvec = np.linalg.eig(I_AAd)
sq_I_AAd = eigvec * np.sqrt(eigval) @ np.linalg.inv(eigvec)
I_AdA = np.identity(n) - A_dag @ A
eigval, eigvec = np.linalg.eig(I_AdA)
sq_I_AdA = eigvec * np.sqrt(eigval) @ np.linalg.inv(eigvec)
U = np.zeros(shape=(2 * n, 2 * n), dtype=complex)
U[0:n, 0:n] = A
U[0:n, n:] = sq_I_AAd
U[n:, 0:n] = sq_I_AdA
U[n:, n:] = -A_dag
return U
接著,我們要處理角度序列的慣例。底下實作了從 Wx
轉換至 R
的方法 (據此處 Corollary 8):
def convert_convention(Wx_seq: list) -> tuple:
R_seq = np.zeros(len(Wx_seq))
# 這裡的 d 正是 QSVT 定理中的 d
d = len(Wx_seq) - 1
# R-convention 的序列長度比 Wx-convention 的長度少 1 (R_seq[0] 用不到)
R_seq[1] = Wx_seq[0] + Wx_seq[d] + (d - 1) * np.pi / 2
for j in range(2, d + 1):
R_seq[j] = Wx_seq[j - 1] - np.pi / 2
return (d, R_seq)
還有一個很重要的部分是,如何實作「對 所投影到的空間進行 phase shift」?如下圖所示 (圖來源:A Grand Unification of Quantum Algorithms):
具體而言,若 ,則
不過呢,由於我們 QSVT 的 相當簡單,因此我們只需要 CNOT:(假設 q1
是用來 block-encode A
的 qubit,而 q2
和 q3
則是 A
本身)
程式實作類似於底下這段:
from qiskit import QuantumCircuit
qc = QuantumCircuit(4)
...
qc.cx(control_qubit=1, target_qubit=0, ctrl_state=0)
qc.rz(phi=phi_s, qubit=0)
qc.cx(control_qubit=1, target_qubit=0, ctrl_state=0)
而此電路還可以進一步簡化:將輔助 qubit q0
省去!(但若要實作 ,我們需要 LCU 的想法 (昨天稍有提到),此時 q0
就是必須的)
QSVT 基本框架的實作告一段落了,明天來實作 QSVT 的應用!